package com.tuling.code.algorithm.sort.exam;

/**
 * 有两个已经排好序的数组，尽量使用最少时间复杂度，将两个数组合并为一个新的排好序的数组
 * 
 * @author javaw
 *
 */
public class MergeSort {
	public static void main(String[] args) {
		int[] b = { 1, 3, 5, 7, 9, 11 };
		int[] a = { 2, 4, 6, 8, 10, 12, 13 };
		
		int[]result = mergeSort(a, b);
		for (int i : result) {
			System.out.print(i + " , ");
		}
	}

	/**
	 * 合并排序
	 * @param a
	 * @param b
	 * @return
	 */
	private static int[] mergeSort(int[]a , int []b) {
		int aLen = a.length ;
		int bLen = b.length;
		int []result = new int[aLen + bLen];
		 //i指向A数组的当前下标， j指向B数组的当前下标
		int i =0, j =0 ;
		int idx = 0;
		while (i<aLen || j<bLen) {
			if(i == aLen && j < bLen){
				//如果数组A已经到了末尾，数组B还没有 , 直接将B数组的剩余数据追加到结果数组中
				result[idx] = b[j];
				idx++;
				j++;
			} else if(i < aLen && j == bLen){
				//如果数组A还没有到末尾，而数组B已经结束了，则直接将A数组剩下的数据直接追加到结果数组中
				result[idx] = a[i];
				idx ++;
				i++;
			} else {
				if(a[i] < b[j]){
					result[idx] = a[i];
					idx++;
					i++;
				} else if(a[i] > b[j]){
					result[idx] = b[j];
					idx ++ ;
					j++;
				}
			}
		}
		return result;
	}
}
